package algocasts;

public class P44_isValidBST {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    TreeNode min(TreeNode root) {
        while (root.left != null) root = root.left;
        return root;
    }

    TreeNode max(TreeNode root) {
        while (root.right != null) root = root.right;
        return root;
    }

    // Time:P(m*log(n)) Space:O(n)
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean leftValid = root.left == null || root.val > max(root.left).val;
        boolean rightValid = root.right == null || root.val < min(root.right).val;
        return leftValid && rightValid && isValidBST(root.left) && isValidBST(root.right);
    }

    boolean isValidBSTBound(TreeNode root, TreeNode lower, TreeNode upper) {
        if (root == null) return true;
        if (lower != null && lower.val >= root.val) return false;
        if (upper != null && upper.val <= root.val) return false;
        return isValidBSTBound(root.left, lower, root) && isValidBSTBound(root.right, root, upper);
    }

    public boolean isValidBSTBound(TreeNode root) {
        return isValidBSTBound(root, null, null);
    }

}
